//复习一下各种排序
//递归一定记得写递归出口

#include <iostream>
#include <stack>
#include <vector>
using namespace std;

void quickSort(vector<int> &nums, int left, int right)
{
    //递归出口
    if (left >= right)
        return;
    int mark = nums[left];
    int pivot = left;
    for (int i = left; i <= right; ++i) {
        if (nums[i] < mark) {
            pivot++;
            swap(nums[i], nums[pivot]); // 大数上浮
        }
    }
    // 至此，大于mark的数已经移到pivot右部
    swap(nums[left], nums[pivot]);
    quickSort(nums, left, pivot - 1);
    quickSort(nums, pivot + 1, right);
}

void quickSort2(vector<int> &nums, int left, int right)
{
    using PAIR = pair<int, int>;
    stack<PAIR> stk;
    stk.push(PAIR(left, right));
    while (!stk.empty()) {
        auto temp = stk.top();
        stk.pop();
        left = temp.first, right = temp.second;
        if (left >= right)
            continue;
        int mark = nums[left];
        int pivot = left;
        for (int i = left; i <= right; ++i) {
            if (nums[i] < mark) {
                pivot++;
                swap(nums[i], nums[pivot]);
            }
        }
        swap(nums[left], nums[pivot]);
        stk.push(PAIR(left, pivot - 1));
        stk.push(PAIR(pivot + 1, right));
    }
}

void adjustHeap(vector<int> &nums, int parent, int length)
{
    int son = 2 * parent + 1;
    while (son < length) {
        if (son + 1 < length && nums[son] < nums[son + 1])
            son++; //大顶堆
        if (nums[son] < nums[parent])
            break;
        swap(nums[son], nums[parent]);
        parent = son;
        son = 2 * parent + 1;
    }
}

void heapSort(vector<int> &nums, int length)
{
    //build heap O(N)
    for (int i = length / 2 - 1; i >= 0; --i) {
        adjustHeap(nums, i, length);
    }
    swap(nums[0], nums[length - 1]);
    for (int i = 1; i < length; ++i) {
        adjustHeap(nums, 0, length - i);
        swap(nums[0], nums[length - i - 1]);
    }
}

void mergeSort(vector<int> &nums, vector<int> &temp, int left, int right)
{
    if (left >= right)
        return;
    int mid = left + (right - left) / 2;
    mergeSort(nums, temp, left, mid);
    mergeSort(nums, temp, mid + 1, right);
    int i = left, j = mid + 1, k = 0;
    while (i <= mid && j <= right) {
        if (nums[i] < nums[j])
            temp[k++] = nums[i++];
        else
            temp[k++] = nums[j++];
    }
    while (i <= mid)
        temp[k++] = nums[i++];
    while (j <= right)
        temp[k++] = nums[j++];
    k = 0;
    for (int i = left; i <= right; ++i)
        nums[i] = temp[k++];
}

void printVec(const vector<int> &nums)
{
    for (auto &num : nums)
        cout << num << " ";
    cout << endl;
}
int main()
{
    vector<int> nums = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
    printVec(nums);
    // quickSort(nums, 0, nums.size() - 1);
    // quickSort2(nums, 0, nums.size() - 1);
    // heapSort(nums, nums.size());
    vector<int> temp(nums.size(), 0);
    mergeSort(nums, temp, 0, nums.size() - 1);
    printVec(nums);
    return 0;
}